package MonotonicStack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 42. 接雨水
 * 困难
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
 */
public class trap {
    //一刷
    /**
     * 单调栈解法
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int size = height.length;
        if (size <= 2) return 0;
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        int sum = 0;
        for (int index = 1; index < size; index++) {
            if (height[index] < height[stack.peek()]) {
                stack.push(index);
            } else if (height[index] == height[stack.peek()]) {
                stack.pop();    // 这个可以加，可以不加，效果一样，思路不同,如果不加的话，下面计算的时候h就直接为0，不会计入，所以加不加一样
                stack.push(index);
            } else {
                while (!stack.isEmpty() && (height[index] > height[stack.peek()])) {
                    int mid = stack.pop();
                    if (!stack.isEmpty()) {
                        int left = stack.peek();
                        int h = Math.min(height[left], height[index]) - height[mid];
                        int w = index - left - 1;
                        int hold = h * w;
                        sum += hold;
                    }
                }
                stack.push(index);
            }
        }
        return sum;
    }

    /**
     * 双指针解法
     *
     * @param height
     * @return
     */
    public static int trap2(int[] height) {
        if (height == null || height.length < 3) return 0;
        int[] maxleft = new int[height.length];
        int[] maxright = new int[height.length];
        maxleft[0] = height[0];
        maxright[height.length - 1] = height[height.length - 1];
        for (int i = 1; i < height.length; i++) {
            maxleft[i] = Math.max(maxleft[i - 1], height[i]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            maxright[i] = Math.max(maxright[i + 1], height[i]);
        }
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            res += Math.min(maxleft[i], maxright[i]) - height[i];
        }
        return res;
    }

    /**
     * 二刷
     */
    class Solution {
        public int trap(int[] height) {
            Deque<Integer> stack = new ArrayDeque<>();
            int sum = 0;
            stack.push(0);
            for (int i = 1; i < height.length; i++) {
                while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                    int mid = stack.pop();
                    if (!stack.isEmpty()) {
                        int left = stack.peek();
                        int h = Math.min(height[i], height[left]) - height[mid];
                        sum += h * (i - left - 1);
                    }
                }
                stack.push(i);
            }
            return sum;
        }
    }

}
